/**
 * //You are given an integer array coins representing coins of different
 * //denominations and an integer amount representing a total amount of money.
 * //
 * // Return the number of combinations that make up that amount. If that amount
 * //of money cannot be made up by any combination of the coins, return 0.
 * //
 * // You may assume that you have an infinite number of each kind of coin.
 * //
 * // The answer is guaranteed to fit into a signed 32-bit integer.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: amount = 5, coins = [1,2,5]
 * //Output: 4
 * //Explanation: there are four ways to make up the amount:
 * //5=5
 * //5=2+2+1
 * //5=2+1+1+1
 * //5=1+1+1+1+1
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: amount = 3, coins = [2]
 * //Output: 0
 * //Explanation: the amount of 3 cannot be made up just with coins of 2.
 * //
 * //
 * // Example 3:
 * //
 * //
 * //Input: amount = 10, coins = [10]
 * //Output: 1
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= coins.length <= 300
 * // 1 <= coins[i] <= 5000
 * // All the values of coins are unique.
 * // 0 <= amount <= 5000
 * //
 * //
 * // Related Topics 数组 动态规划 👍 900 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00518CoinChange2 {
    public static void main(String[] args) {
        Solution solution = new ID00518CoinChange2().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int change(int amount, int[] coins) {

            //status 用来存放状态，每个下标表示能达到的amount，值表示多少条way
            int[] status = new int[amount + 1];

            //初始化status
            status[0] = 1; //每个coin从0到该coin的面值都是一条way
            //每个amount的可达的way，等于前一个way + amount的way
            //动态规划
            for (int i = 0; i < coins.length; ++i) {
                for (int j = 0; j <= amount; ++j) {
                    if (j + coins[i] <= amount) {
                        status[j + coins[i]] += status[j];//每个amount的可达的way，等于前一个way + amount的way
                    }
                }
            }
            return status[amount];


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}